{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Hidden Sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfArrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计隐藏数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始且长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>differences</code>&nbsp;，它表示一个长度为&nbsp;<code>n + 1</code>&nbsp;的&nbsp;<strong>隐藏</strong>&nbsp;数组&nbsp;<strong>相邻</strong>&nbsp;元素之间的&nbsp;<strong>差值</strong>&nbsp;。更正式的表述为：我们将隐藏数组记作&nbsp;<code>hidden</code>&nbsp;，那么&nbsp;<code>differences[i] = hidden[i + 1] - hidden[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你两个整数&nbsp;<code>lower</code> 和&nbsp;<code>upper</code>&nbsp;，它们表示隐藏数组中所有数字的值都在 <strong>闭</strong>&nbsp;区间&nbsp;<code>[lower, upper]</code>&nbsp;之间。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>differences = [1, -3, 4]</code>&nbsp;，<code>lower = 1</code>&nbsp;，<code>upper = 6</code>&nbsp;，那么隐藏数组是一个长度为 <code>4</code>&nbsp;且所有值都在&nbsp;<code>1</code>&nbsp;和&nbsp;<code>6</code>&nbsp;（包含两者）之间的数组。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><code>[3, 4, 1, 5]</code> 和&nbsp;<code>[4, 5, 2, 6]</code>&nbsp;都是符合要求的隐藏数组。</li>\n",
    "\t\t<li><code>[5, 6, 3, 7]</code>&nbsp;不符合要求，因为它包含大于 <code>6</code>&nbsp;的元素。</li>\n",
    "\t\t<li><code>[1, 2, 3, 4]</code>&nbsp;不符合要求，因为相邻元素的差值不符合给定数据。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <strong>符合</strong>&nbsp;要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>differences = [1,-3,4], lower = 1, upper = 6\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>符合要求的隐藏数组为：\n",
    "- [3, 4, 1, 5]\n",
    "- [4, 5, 2, 6]\n",
    "所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>differences = [3,-4,5,1,-2], lower = -4, upper = 5\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>符合要求的隐藏数组为：\n",
    "- [-3, 0, -4, 1, 2, 0]\n",
    "- [-2, 1, -3, 2, 3, 1]\n",
    "- [-1, 2, -2, 3, 4, 2]\n",
    "- [0, 3, -1, 4, 5, 3]\n",
    "所以返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>differences = [4,-7,2], lower = 3, upper = 6\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有符合要求的隐藏数组，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == differences.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= differences[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= lower &lt;= upper &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-hidden-sequences](https://leetcode.cn/problems/count-the-hidden-sequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-hidden-sequences](https://leetcode.cn/problems/count-the-hidden-sequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-3,4]\\n1\\n6', '[3,-4,5,1,-2]\\n-4\\n5', '[4,-7,2]\\n3\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        mx = 0\n",
    "        mn = 0\n",
    "        for a in accumulate(differences):\n",
    "            if a > mx:\n",
    "                mx = a\n",
    "            elif a < mn:\n",
    "                mn = a\n",
    "        return max(0, upper - lower - (mx - mn) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = 0\n",
    "        minVal, maxVal = 0, 0\n",
    "        for i in range(len(differences)):\n",
    "            n += differences[i]\n",
    "            minVal = min(minVal, n)\n",
    "            maxVal = max(maxVal, n)\n",
    "\n",
    "        maxDiff = maxVal - minVal\n",
    "        ans = (upper - lower) - maxDiff + 1\n",
    "        return max(0, ans) # 如果还原后的数组跨度大于upper-lower，则没有有效解\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        x = y = cur = 0\n",
    "        for d in differences:\n",
    "            cur += d\n",
    "            x = min(x, cur)\n",
    "            y = max(y, cur)\n",
    "            if y - x > upper - lower:\n",
    "                return 0\n",
    "        return (upper - lower) - (y - x) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "\n",
    "        if len(differences) == 1:\n",
    "            return max(upper - lower -abs(differences[0]) + 1,0)\n",
    "        s = 0\n",
    "        ma = 0\n",
    "        mi = 0\n",
    "        for i in differences:\n",
    "            s += i\n",
    "            if s > ma:\n",
    "                ma = s\n",
    "            if s < mi:\n",
    "                mi = s\n",
    "        return max(upper - lower - ma + mi + 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        s = 0\n",
    "        mx = -inf\n",
    "        mn = inf\n",
    "        for d in differences:\n",
    "            s += d\n",
    "            mx = max(mx, s)\n",
    "            mn = min(mn, s)\n",
    "        return max(0, min(upper - mx, upper) - max(lower - mn, lower) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        mx = mn = 0\n",
    "        for a in accumulate(differences):\n",
    "            if a > mx:\n",
    "                mx = a\n",
    "            elif a < mn:\n",
    "                mn = a\n",
    "            if mx - mn > upper - lower:\n",
    "                return 0\n",
    "        return upper - lower - (mx - mn) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        mx = mn = 0\n",
    "        for a in accumulate(differences):\n",
    "            if a > mx:\n",
    "                mx = a\n",
    "            elif a < mn:\n",
    "                mn = a\n",
    "            if mx - mn > upper - lower:\n",
    "                return 0\n",
    "        return upper - lower - (mx - mn) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        xx=[]\n",
    "        xx.append(0)\n",
    "        x=0\n",
    "        p=0\n",
    "        q=0\n",
    "        for i in differences:\n",
    "            x+=i\n",
    "            xx.append(x)\n",
    "            if x<p:\n",
    "                p=x\n",
    "            if x>q:\n",
    "                q=x\n",
    "        #print(p,q)\n",
    "        if q-p>upper-lower:\n",
    "            return 0\n",
    "        return (upper-lower)-(q-p)+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, a: List[int], l: int, r: int) -> int:\n",
    "        n = len(a)\n",
    "        \n",
    "        l1, r1 = l, r\n",
    "        for i in range(n):\n",
    "            l1 += a[i]\n",
    "            r1 += a[i]\n",
    "            l1 = max(l, l1)\n",
    "            r1 = min(r, r1)\n",
    "            \n",
    "            if l1 > r1: return 0\n",
    "        \n",
    "        return r1 - l1 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        mx = mn = 0\n",
    "        for a in accumulate(differences):\n",
    "            if a > mx:\n",
    "                mx = a\n",
    "            elif a < mn:\n",
    "                mn = a\n",
    "        return max(0, upper - lower - (mx - mn) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        def check(m):\n",
    "            mx, mn = m, m\n",
    "            for x in differences:\n",
    "                m += x\n",
    "                mx, mn = max(mx, m), min(mn, m)\n",
    "            return mn, mx\n",
    "        l, r = lower, upper + 1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            mn, mx = check(mid)\n",
    "            if mn >= lower:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        mn, mx = check(l)\n",
    "        if mn < lower or mx > upper: return 0\n",
    "        \n",
    "        p = l\n",
    "        \n",
    "        l, r = lower, upper + 1\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            mn, mx = check(mid)\n",
    "            if mx <= upper:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        mn, mx = check(l)\n",
    "        if mn < lower or mx > upper: return 0\n",
    "        return l - p + 1\n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "            \n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        pre = list(accumulate(differences))\n",
    "        mi = min(pre)\n",
    "        ma = max(pre)\n",
    "        l1, r1 = lower-mi, upper-mi\n",
    "        l2, r2 = lower-ma, upper-ma\n",
    "        \n",
    "        left = max(l1, l2)\n",
    "        right= min(r1, r2)\n",
    "        \n",
    "        left= max(left, lower)\n",
    "        right = min(right, upper)\n",
    "        \n",
    "        return max(0, right-left+1)\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        Max = -inf\n",
    "        Min = inf\n",
    "        init = 0\n",
    "        Max = max(Max,init)\n",
    "        Min = min(Min,init)\n",
    "        for i in differences:\n",
    "            init+=i\n",
    "            Max = max(Max,init)\n",
    "            Min = min(Min,init)\n",
    "        Max += (lower-Min)\n",
    "        Min += (lower-Min)\n",
    "        return max(0,upper-Max+1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        v,mx,mn = 0,0,0\n",
    "        for i in differences:\n",
    "            v += i\n",
    "            mx = max(mx,v)\n",
    "            mn = min(mn,v)\n",
    "        res = (upper-lower - (mx-mn))+1\n",
    "        return res if res > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = 0\n",
    "        minVal, maxVal = 0, 0\n",
    "        for i in range(len(differences)):\n",
    "            n += differences[i]\n",
    "            minVal = min(minVal, n)\n",
    "            maxVal = max(maxVal, n)\n",
    "\n",
    "        maxDiff = maxVal - minVal\n",
    "        ans = (upper - lower) - maxDiff + 1\n",
    "        return max(0, ans) # 如果还原后的数组跨度大于upper-lower，则没有有效解\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        def check(m):\n",
    "            mx, mn = m, m\n",
    "            for x in differences:\n",
    "                m += x\n",
    "                mx, mn = max(mx, m), min(mn, m)\n",
    "            return mn, mx\n",
    "        l, r = lower, upper + 1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            mn, mx = check(mid)\n",
    "            if mn >= lower:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        mn, mx = check(l)\n",
    "        if mn < lower or mx > upper: return 0\n",
    "        \n",
    "        p = l\n",
    "        \n",
    "        l, r = lower, upper + 1\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            mn, mx = check(mid)\n",
    "            if mx <= upper:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        mn, mx = check(l)\n",
    "        if mn < lower or mx > upper: return 0\n",
    "        return l - p + 1\n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "            \n",
    "        \n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(differences)\n",
    "        nums = [0] * (n + 1)\n",
    "        # d[i] = nums[i + 1] - nums[i]\n",
    "        # d[i - 1] = nums[i] - nums[i - 1]\n",
    "        s = differences[0]\n",
    "        max_increment = s\n",
    "        min_increment = s\n",
    "        for i in range(1, n):\n",
    "            s += differences[i]\n",
    "            max_increment = max(max_increment, s)\n",
    "            min_increment = min(min_increment, s)\n",
    "        return max(min(upper, upper - max_increment) - max(lower, lower - min_increment) + 1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        hidden = list(accumulate(differences, initial=0))\n",
    "        mx, mn = max(hidden), min(hidden)\n",
    "        if lower - mn <= upper - mx:\n",
    "            return upper - mx - lower + mn + 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        x = y = cur = 0\n",
    "        for d in differences:\n",
    "            cur += d\n",
    "            x = min(x, cur)\n",
    "            y = max(y, cur)\n",
    "            if y - x > upper - lower:\n",
    "                return 0\n",
    "        return (upper - lower) - (y - x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        pr=0\n",
    "        mi=0\n",
    "        ans=0\n",
    "        cur=0\n",
    "        for x in differences:\n",
    "          cur+=x\n",
    "          if cur>pr:\n",
    "             pr=cur\n",
    "          if cur<mi:\n",
    "             mi=cur\n",
    "          ans=max(ans,pr-mi)\n",
    "        if upper-lower<ans:\n",
    "            return 0\n",
    "        return upper-lower-ans+1     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = 0\n",
    "        minVal, maxVal = 0, 0\n",
    "        for i in range(len(differences)):\n",
    "            n += differences[i]\n",
    "            minVal = min(minVal, n)\n",
    "            maxVal = max(maxVal, n)\n",
    "\n",
    "        maxDiff = maxVal - minVal\n",
    "        ans = (upper - lower) - maxDiff + 1\n",
    "        return max(0, ans) # 如果还原后的数组跨度大于upper-lower，则没有有效解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        x = maxnum = minnum = 0\n",
    "        n = len(differences)\n",
    "        for i in differences:\n",
    "            x += i \n",
    "            maxnum = max(maxnum, x)\n",
    "            minnum = min(minnum, x)\n",
    "        ans = minnum - maxnum - lower + upper + 1\n",
    "        return max(ans, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(differences)\n",
    "        diff = [differences[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(differences[i]+diff[-1])\n",
    "        minnum, maxnum = lower, upper\n",
    "        for d in diff:\n",
    "            minnum = max(minnum, lower-d)\n",
    "            maxnum = min(maxnum, upper-d)\n",
    "        return max(maxnum-minnum+1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param differences:\n",
    "        :param lower:\n",
    "        :param upper:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        min1 = 0\n",
    "        max1 = 0\n",
    "        prev = 0\n",
    "        for (k, v) in enumerate(differences):\n",
    "            prev += v\n",
    "            min1 = min(min1, prev)\n",
    "            max1 = max(max1, prev)\n",
    "        delta = upper - lower - (max1 - min1) + 1\n",
    "        return max(0, delta)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        s=0\n",
    "        maxm=differences[0]\n",
    "        minm=differences[0]\n",
    "        for i in range(0,len(differences)):\n",
    "            s=s+differences[i]\n",
    "            print(s)\n",
    "            maxm=max(maxm,s)\n",
    "            minm=min(minm,s)\n",
    "\n",
    "            if upper-maxm<lower or lower-minm>upper or maxm-minm>upper-lower:\n",
    "                return 0\n",
    "        if maxm==minm:\n",
    "            return upper-lower-abs(maxm)+1\n",
    "        else:\n",
    "            return min(upper-maxm,upper)-max(lower,lower-minm)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        x = y = cur = 0\n",
    "        for d in differences:\n",
    "            cur += d\n",
    "            x = min(x, cur)\n",
    "            y = max(y, cur)\n",
    "            if y - x > upper - lower:\n",
    "                return 0\n",
    "        return (upper - lower) - (y - x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        lst = list(accumulate(differences, initial = 0))\n",
    "        return max(0, upper - lower + min(lst) - max(lst) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(differences)\n",
    "        diff = [differences[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(differences[i]+diff[-1])\n",
    "        minnum, maxnum = lower, upper\n",
    "        for d in diff:\n",
    "            minnum = max(minnum, lower-d)\n",
    "            maxnum = min(maxnum, upper-d)\n",
    "        return max(maxnum-minnum+1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        hidden = list(accumulate(differences))\n",
    "        ans = min(upper-max(hidden), upper) - max(lower, lower-min(hidden)) +1 \n",
    "        return max(0, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        arr=list(itertools.accumulate(differences,initial=0))\n",
    "        max_num=max(arr)\n",
    "        min_num=min(arr)\n",
    "        # a+min_num>=lower\n",
    "        # a+max_num<=upper\n",
    "        if lower-min_num<=upper-max_num:\n",
    "            return upper-max_num-lower+min_num+1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        hidden = list(accumulate(differences))\n",
    "        mx, mn = max(hidden), min(hidden)\n",
    "        ret = 0\n",
    "        for h in range(lower - mn, upper - mx + 1):\n",
    "            if lower <= h <= upper:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        pre = list(accumulate(differences, initial=0))\n",
    "        return max(0, upper-lower-(max(pre)-min(pre))+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        mx = mn = 0\n",
    "        for a in accumulate(differences):\n",
    "            if a > mx:\n",
    "                mx = a\n",
    "            elif a < mn:\n",
    "                mn = a\n",
    "        return max(0, upper - lower - (mx - mn) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(differences)\n",
    "        mi = ma = differences[0]\n",
    "        for i in range(1, n):\n",
    "            differences[i] += differences[i - 1]\n",
    "            mi = min(mi, differences[i])\n",
    "            ma = max(ma, differences[i])\n",
    "        lower = max(lower, lower - mi)\n",
    "        upper = min(upper, upper - ma)\n",
    "        return max(0, upper - lower + 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
